package com.itheima.leetcode;

/**
 * 小顶堆
 *
 * @FileName MinHeap
 * @Description
 * @Author Sword
 * @date 2025-05-21
 **/
public class MinHeap {

    /*
                        p
        1 -> 4 -> 5 -> null

                        p
        1 -> 3 -> 4 -> null

                    p
        2 -> 6 -> null

        小顶堆
        空链表 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6
     */

    ListNode[] array;
    int size;

    public MinHeap(int capacity) {
        array = new ListNode[capacity];
    }

    /*
        1. 入堆新元素，加入到数组末尾（索引位置child）
        2. 不断比较新加入元素与它父节点（parent）优先级
            - 如果父节点优先级高，则向下移动，并找到下一个parent
            - 直至父节点优先级更低或 child==0 为止
     */
    public boolean offer(ListNode offered) {
        if (isFull()) {
            return false;
        }
        int child = size++;
        int parent = (child - 1) / 2;
        while (child > 0 && offered.val < array[parent].val) {
            array[child] = array[parent];
            child = parent;
            parent = (child - 1) / 2;
        }
        array[child] = offered;
        return true;
    }

    /*
        1. 交换堆顶和尾部元素，让尾部元素出队
        2.（下潜）
            - 从堆顶开始，将父元素与两个孩子较小者交换
            - 直到父元素小于两个孩子，或没有孩子为止
     */
    public ListNode poll() {
        if (isEmpty()) {
            return null;
        }

        swap(0, size - 1);
        size--;
        ListNode node = array[size];
        array[size] = null; //help GC
        down(0);

        return node;

    }

    private void swap(int i, int j) {
        ListNode t = array[i];
        array[i] = array[j];
        array[j] = t;
    }

    private void down(int parent) {
        int left = parent * 2 + 1;
        int right = left + 1;

        int min = parent;   //假设父元素优先级最低

        if (left < size && array[left].val < array[min].val) {
            min = left;
        }

        if (right < size && array[right].val < array[min].val) {
            min = right;
        }

        if (min != parent) {
            swap(min, parent);
            down(min);
        }
    }

    public ListNode peek() {
        if (isEmpty()) {
            return null;
        }

        return array[0];
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public boolean isFull() {
        return size == array.length;
    }
}
